The invention relates generally to the field of digital communications, and more particularly to systems and methods for switching packets of digital data in a switching node used in a digital data network.
Digital networks have been developed to facilitate the transfer of information, including data and programs, among digital computer systems and numerous other types of devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In modem networks, information is transferred through a mesh of switching nodes which are interconnected by communication links in a variety of patterns. The mesh interconnection pattern can allow for a number of paths to be available through the network from each computer system or other device which may transmit information as a source device, to another computer system or other device, which is to receive the information as a destination device, so that if congestion develops in particular regions of the network, or if components of the network become inoperative, information can be routed around the congested or inoperative portion of the network.
Information transferred from a source device to a destination device is generally transferred in the form of fixed- or variable-length packets, which are received by a switching node over one communication link connected thereto, and transmitted over another communication link to facilitate transfer of the packet to the destination device or another switching node along a path to the destination device. Each packet typically includes address information, including a source address that identifies the particular device that generated the packet, and a destination address that identifies the particular device or devices to receive the packet.
Typically, a switching node includes one or more input ports, each of which is connected to a communication link to receive packets, a plurality of output ports, each of which is connected to a communication link to transmit packets, and a xe2x80x9cswitching fabricxe2x80x9d that couples packets from the input ports to the respective output ports for transmission. After an input port receives a packet, it will typically buffer the packet, identify from the destination address the particular output port that is to transmit the packet and transfer the packet to the output port through the switching fabric. After the output port receives the packet, it (that is, the output port) will typically buffer the packet in a queue for transmission over the communication link connected thereto. While buffering and scheduling by the output port can provide for efficient packet transmission by the output port, since the output port can be kept continually busy, several problems can arise with output port buffering. Generally, each output port will effectively provide one queue for each input port, in which case the total number of queues provided by the switching node will be on the order of N2, where xe2x80x9cNxe2x80x9d is the number of input ports, which, in turn, corresponds to the number of output ports, if, as is typical, each communication link provides for bi-directional transmission of packets. Thus, as xe2x80x9cN,xe2x80x9d the number of input/output ports, increases, the number of queues maintained by the output ports increases quadratically, at a much faster rate, and so output queuing does not scale well.
Instead of using output queuing of packets to be transmitted, switching nodes have been developed which can provide input queuing, in which packets are buffered and queued at the input ports. Only one queue is needed for each input port, and so, as the number of input (and output) ports increases, the number of queues increases at a linear rate, avoiding the quadratic increase with output queuing. However, input queuing results in much lower efficiency of usage of the switching fabric, since the input ports must, after buffering received packets, essentially contend and arbitrate for use of the switching fabric to facilitate transfer of the packets to the respective output ports for transmission.
The invention provides a new and improved switching node which provides for the efficient use of the switching fabric interconnecting input and output ports that is characteristic of a switching node that provides for output-queuing of packets transferred by the switching node, while avoiding the quadratic increase in packet queues, relative to increasing numbers of input/output ports, that is characteristic of switching nodes that provide for output-queuing. Similarly, the invention provides a new and improved switching node which provides for the linear increase in packet queues, relative to increasing numbers of input/output ports, that is characteristic of switching nodes that provide for input queuing, while avoiding the relative inefficient usage of the switching fabric interconnecting input and output ports that is characteristic of a switching node that provides for input-queuing of packets transferred by the switching node.
In brief summary, the invention provides a switching node, including a plurality of input port modules, a plurality of output port modules and a switching fabric for transferring packets in a network, each packet including a destination address. Each input port module is connected to a communication link for receiving packets thereover, and each output port module is connected to a communication link for transmitting packets thereover. Each input port module, upon receiving a packet from the communication link connected thereto, buffers the packet and generates a meta-data packet therefor, the meta-data packet identifying the output port module that is to transmit the packet, and generates identifier information for the packet, in particular the identification of the input port module in which the packet is buffered and a pointer to the location in the input port module in which the packet is buffered. After generating the meta-data packet, the input port module provides it to the switching fabric, in particular to a packet meta-data processor portion thereof.
The switching fabric includes both the packet meta-data processor portion and a packet switch portion. The packet meta-data processor portion receives the meta-data packets generated by all of the input port modules and operational status information from all of the output port modules. The operational status information for each output port module includes information that is useful in making a determination for each respective output port module as to whether or not packets that would be transmitted by the respective output port module are to be discarded, or dropped. For each output port module, the packet meta-data processor processes the meta-data packets received from all of the input port modules in connection with the operational status information. If, in processing a meta-data packet, the packet meta-data processor determines that the packet associated with the meta-data packet is to be dropped, it will notify the input port module in which the packet is buffered, which, in turn, will discard the packet. On the other hand, if the packet meta-data processor determines that the packet associated with the meta-data packet is not to be dropped, it will enqueue the meta-data packet for the associated output port module.
Each output port module retrieves meta-data packets from its respective meta-data packet queue maintained therefor by the packet meta-data processor. For each meta-data packet retrieved by an output port module, the output port module will issue a request to the input port module identified in the meta-data packet to transfer the packet identified in the input port module to it (that is, to the output port module that issued the request). The input port module, after receiving the request from the output port module, will transfer the requested packet through the packet switch portion of the switching fabric. The packet switch portion, in turn, will transfer the packet to the output port module, for transmission thereby over the communication link connected thereto.
A switching node constructed in accordance with the invention provides the scalability of a input-queued switching node, while maintaining substantially the efficiency of switching fabric usage of an output-queued switching node. Since the packets are buffered at the input port modules until the determination has been made by the packet meta-data processor that they are to be transmitted by respective output port modules, and further until they are requested by the respective output port modules for to be transferred thereto for transmission, only xe2x80x9cNxe2x80x9d buffers, or queues, are needed, one for each input port module, whereas in an output-queued switching node N2 buffers would be required. However, the determination as to which packets should be discarded (that is, which packets should be dropped) and which should not be (that is, which packets should be passed), is made separately for each output port module effectively in a queue established therefor, and so the pass/drop determinations are effectively made in a manner similar to that for an output queued switching node. Thus, the packet switch portion of the switching fabric an achieve efficiencies similar to those achieved in output queued switching nodes.